//给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 
//
// 你可以按 任何顺序 返回答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 4, k = 2
//输出：
//[
//  [2,4],
//  [3,4],
//  [2,3],
//  [1,2],
//  [1,3],
//  [1,4],
//] 
//
// 示例 2： 
//
// 
//输入：n = 1, k = 1
//输出：[[1]] 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 20 
// 1 <= k <= n 
// 
//
// Related Topics 回溯 👍 1409 👎 0


import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> tem = new ArrayList<>();
        backtrace(1,n,k,result,tem);
        return result;
    }
    public void backtrace(int start,int n,int k, List<List<Integer>> result, List<Integer> tem){
        if(k==0){
            result.add(new ArrayList<>(tem));
            return;
        }
        for (int i = start; i <=n ; i++) {
            tem.add(i);
            backtrace(i+1,n,k-1,result,tem);
            tem.remove(tem.size()-1);
        }
    }
}

//leetcode submit region end(Prohibit modification and deletion)
